package codingforgreat.class06;

import java.security.PublicKey;

public class Class03_MaximumXorWithAnElementFromArray {

    public class Node{
       public Node[] nexts;
       public int min;
        public Node() {
            min = Integer.MAX_VALUE;
            nexts = new Node[2];
        }
    }

    public class TireTree{
        public Node head = new Node();

        public void add(int num){
            Node cur = head;
            head.min = Math.min(head.min,num);
            for (int i = 31; i >= 0 ; i--) {
                int path = ((num >> i) & 1);
                cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
                cur = cur.nexts[path];
                cur.min = Math.min(cur.min, num);
            }
        }

        public int getMaxXor(int num,int m){

            if(head.min > m){
                return -1;
            }
            int res = 0;
            Node cur = head;
            for (int i = 30; i >= 0 ; i--) {
                int path = (num >> i) & 1;
                int best =  (path ^ 1);
                best = (cur.nexts[best] != null && cur.nexts[best].min <= m) ? best : best ^ 1;
                res |= (path ^ best) << i;
                cur = cur.nexts[best];
            }
            return res;

        }


    }
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int N = nums.length;
        TireTree trie = new TireTree();
        for (int i = 0; i < N; i++) {
            trie.add(nums[i]);
        }
        int M = queries.length;
        int[] ans = new int[M];
        for (int i = 0; i < M; i++) {
            ans[i] = trie.getMaxXor(queries[i][0], queries[i][1]);
        }
        return ans;
    }
}
